package com.zjsru.oneDay202204;

/**
 * @Author: likew
 * @Date: 2022/4/16
 *
 * 最大回文数乘积
 * 给定一个整数 n ，返回 可表示为两个 n 位整数乘积的 最大回文整数 。因为答案可能非常大，所以返回它对 1337 取余 。
 *
 * 输入：n = 2
 * 输出：987
 * 解释：99 x 91 = 9009, 9009 % 1337 = 987
 *
 * 输入： n = 1
 * 输出： 9
 */
public class largestPalindrome {
    /**
     * leetcode超时
     */
//    public int largestPalindrome(int n) {
//        int res = 0,num = 0;
//        int m = (int) Math.pow(10, n) - 1;
//        if(n == 1) return 9;
//        for (int i = 0; i <= m; i++) {
//            for (int j = 0; j <= m; j++) {
//                num = i * j;
//                if(helper(num)){
//                    res = Math.max(num,res);
//                }
//            }
//        }
//        return res % 1337;
//    }
//
//    public boolean helper(int n){
//        //判断是否是回文数
//        if(n < 0 || (n % 10 ==0 && n != 0)){
//            return false;
//        }
//        int x = 0;
//        while(n > x){
//            x = x * 10 + n % 10;
//            n = n/10;
//        }
//        return n == x || n == x /10;
//    }
    
    /**
     * 第二种解法
     * */
    public int largestPalindrome(int n) {
        if(n == 1) return 9;
        int max = (int)Math.pow(10,n) - 1;
        for (int i = max; i >= 0; i--) {
            long num = i,t = i;
            while (t != 0){
                num = num *10 + (t % 10);
                t = t/ 10;
            }
            for (long j = max; j * j >= num ; j--) {
                if(num % j == 0) return (int)(num % 1337);
            }
        }
        return -1;
    }
    
    public static void main(String[] args) {
        largestPalindrome largestPalindrome = new largestPalindrome();
        int n = 5;
        System.out.println(largestPalindrome.largestPalindrome(n));
    }
}
